package leetbook.topInterviewQuestionsEasy;

import java.util.Arrays;

/**
 * 8:45 ~ 9.20 35min
 * 给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Three {

    /**
     * 空间复杂度为O(n)的解法
     * 借助一个辅助数组
     * */
    class Solution {
        public void rotate(int[] nums, int k) {
            int len = nums.length;
            int[] res = new int[len];
            for (int i = 0; i < len; i++) {
                res[(i+k) % len] = nums[i];
            }
            System.arraycopy(res, 0, nums, 0, len);
        }
    }


    /**
     * 空间复杂度O(1)的方法
     * 翻转数组
     * 以 1 2 3 4 5举例 k = 2。
     * 第一步，翻转该数组 变为 5 4 3 2 1
     * 第二步，翻转 0~k-1 这个区域的元素  即 翻转 5 4 为 4 5，当前结果为 4 5 3 2 1
     * 第三步， 翻转 k ~ len 这个区域的元素 即 翻转 3 2 1 为  1 2 3. 最终结果为 4 5 1 2 3
     * */
    class Solution1 {
        public void rotate(int[] nums, int k) {
            if(k == 0){
                return;
            }
            reverse(nums, 0, nums.length-1);
            reverse(nums, 0, (k%nums.length)-1);
            reverse(nums, (k%nums.length), nums.length-1);
        }

        private void reverse(int[] nums, int start, int end){
            while (start < end){
                int t = nums[start];
                nums[start] = nums[end];
                nums[end] = t;
                start++;
                end--;
            }
        }
    }

}
